#include "graph.h"

Graph* create_gp(char* str)
{
    //申请图的内存
    Graph *graph = malloc(sizeof(Graph));
    //备份顶点数量
    graph->vexnum = strlen(str);
    //分配定点空间
    graph->vertex = malloc(graph->vexnum);
    //备份顶点
    strncpy(graph->vertex,str,graph->vexnum);
    graph->edge = calloc(graph->vexnum,graph->vexnum);
    return graph;
}

bool add_eg_gp(Graph* graph, char v1, char v2)
{
    int i1 = get_index_gp(graph,v1);
    int i2 = get_index_gp(graph,v2);
    if(-1 == i1 || -1 == i2 || i1 == i2)
        return false;
    graph->edge[i2*graph->vexnum + i1] = 1;
    return true;
}

int get_index_gp(Graph* graph,char v)
{
    int index = 0;
    while(graph->vertex[index] != v)
        index++;
    return index>graph->vexnum?-1:index;
}

size_t vex_in_gp(Graph* graph, char v)
{
    int cnt = 0,index = get_index_gp(graph,v);
    for(int i = 0; i<graph->vexnum; i++)
    {
        if(graph->vertex[i*graph->vexnum + index])
            cnt++;
    }
    return cnt;
}

size_t vex_out_gp(Graph* graph, char v)
{
    int cnt = 0,index = get_index_gp(graph,v);
    for(int i = 0; i<graph->vexnum; i++)
    {
        if(graph->vertex[index*graph->vexnum + i])
            cnt++;
    }
    return cnt;
}

void _dfs_gp(Graph* graph, int index, bool flags[])
{
    printf("%c ",graph->vertex[index]);
    flags[index] = true;
    for(int i = 0;i < graph->vexnum;i++){
        if(graph->edge[graph->vexnum * i + index] && !flags[i]){
            _dfs_gp(graph,i,flags);
        }
    }
}

void dfs_gp(Graph* graph)
{
    //给所有位置做标记
    bool flags[graph->vexnum];
    bzero(flags,graph->vexnum);
    for(int i = 0;i< graph->vexnum;i++){
        if(!flags[i]){
            _dfs_gp(graph,i,flags);
        }
    }
}

void bfs_gp(Graph* graph)
{
    bool flags[graph->vexnum];
    bzero(flags,graph->vexnum);
    for(int i = 0;i<graph->vexnum;i++){
        if(!flags[i]){
            printf("%c ",graph->vertex[i]);
            flags[i] = true;
        }
        for(int j = 0;j < graph->vexnum;j++){
            if(graph->edge[graph->vexnum*j + i] && !flags[j]){
                printf("%c ",graph->vertex[j]);
                flags[j] = true;
            }
        }
    }
//    bool flags[graph->vexnum];
//    bzero(flags,graph->vexnum);
//    int queue[graph->vexnum],front = 1,rear = 0;
//    for(int i = 0;i < graph->vexnum;i++){
//        if(!flags[i]){
//            queue[rear++] = i;
//        }
//
//        while(front != rear){
//            int index = queue[front++];
//            flags[index] = true;
//            printf("%c ",graph->vertex[index]);
//            for(int j = 0; j<graph->vexnum;j++ ){
//                if(graph->edge[graph->vexnum * j + i] && !flags[j]){
//                    queue[rear++] = j;
//                }
//            }
//        }
//    }
}
